//package org.example.code.eight_mouth;
//
//import java.util.*;
//
//public class code0827 {
//    public void setZeroes(int[][] matrix) {
//        boolean [][]flag = new boolean[matrix.length][matrix[0].length];
//        for(int i=0;i<matrix.length;i++){
//            for(int j=0;j<matrix[0].length;j++){
//                if(matrix[i][j]==0&&!flag[i][j]){
//                    flag[i][j]=true;
//                    change(matrix,i,j,flag);
//                }
//            }
//        }
//    }
//
//    private void change(int[][] matrix, int x, int y, boolean [][]flag) {
//        for(int i=0;i<matrix.length;i++){
//            if(matrix[i][y]==0&&!flag[i][y]){
//                flag[i][y]=false;
//            }else{
//                flag[i][y]=true;
//            }
//            matrix[i][y]=0;
//        }
//        for(int i=0;i<matrix[0].length;i++){
//            if(matrix[x][i]==0&&!flag[x][i]){
//                flag[x][i]=false;
//            }else{
//                flag[x][i]=true;
//            }
//            matrix[x][i]=0;
//        }
//    }
//
//    public List<Integer> spiralOrder(int[][] matrix) {
//        List<Integer> list = new ArrayList<>();
//        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
//            return list;
//        }
//        int l = 0,r = matrix[0].length-1,top = 0,down = matrix.length-1;
//        while(l<=r&&top<=down){
//            for(int i=l;i<=r;i++){
//                list.add(matrix[top][i]);
//            }
//            for(int i=top+1;i<=down;i++){
//                list.add(matrix[i][r]);
//            }
//            if(l<r&&top<down){
//                for(int i=r-1;i>l;i--){
//                    list.add(matrix[down][i]);
//                }
//                for(int i=down;i>top;i--){
//                    list.add(matrix[i][l]);
//                }
//            }
//            l++;
//            r--;
//            top++;
//            down--;
//        }
//        return list;
//    }
//
//    public boolean isPalindrome(ListNode head) {
//        List<ListNode> list = new ArrayList<>();
//        while(head!=null){
//            list.add(head);
//            head = head.next;
//        }
//        int l = 0;
//        int r = list.size()-1;
//        while(l<r){
//            if (list.get(l).val!=list.get(r).val) {
//                return false;
//            }
//            l++;
//            r--;
//        }
//        return true;
//    }
//
//    public boolean hasCycle(ListNode head) {
//        ListNode slow = head;
//        ListNode fast = head;
//        while (fast != null && fast.next != null) {
//            slow = slow.next;
//            fast = fast.next.next;
//            if (slow == fast) {
//                return true;
//            }
//        }
//        return false;
//    }
//
//    public ListNode detectCycle(ListNode head) {
//        ListNode slow = head;
//        ListNode fast = head;
//        while (fast != null && fast.next != null) {
//            slow = slow.next;
//            fast = fast.next.next;
//            if (slow == fast) {
//                fast = head;
//                while (slow != fast) {
//                    slow = slow.next;
//                    fast = fast.next;
//                }
//                return slow;
//            }
//        }
//        return null;
//    }
//
//    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
//        if(list1==null){
//            return list2;
//        }else if(list2==null){
//            return list1;
//        }
//        if(list1.val<list2.val){
//            list1.next = mergeTwoLists(list1.next,list2);
//            return list1;
//        }else{
//            list2.next = mergeTwoLists(list1,list2.next);
//            return list2;
//        }
//    }
//
//    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
//        ListNode head = null, tail = null;
//        int carry=0;
//        while(l1!=null||l2!=null){
//            int n1 = l1!=null?l1.val:0;
//            int n2 = l2!=null?l2.val:0;
//            int sum = n1+n2+carry;
//            if(head==null){
//                head = tail= new ListNode(sum%10);
//            }else{
//                tail.next = new ListNode(sum%10);
//                tail = tail.next;
//            }
//            carry = sum/10;
//            if(l1!=null)
//                l1 = l1.next;
//            if(l2!=null)
//                l2 = l2.next;
//        }
//        if(carry>0){
//            tail.next = new ListNode(carry);
//        }
//        return head;
//    }
//
//    public void rotate(int[][] matrix) {
//        for(int i=0;i<matrix.length/2;i++){
//            for(int j=0;j<matrix[0].length;j++){
//                int t = matrix[i][j];
//                matrix[i][j] = matrix[matrix.length-i-1][j];
//                matrix[matrix.length-i-1][j] = t;
//            }
//        }
//
//        for(int i=0;i< matrix.length;i++){
//            for(int j=0;j<i;j++){
//                int t = matrix[i][j];
//                matrix[i][j] = matrix[j][i];
//                matrix[j][i] = t;
//            }
//        }
//    }
//
//    public boolean searchMatrix(int[][] matrix, int target) {
//        for(int i=0;i<matrix.length;i++){
//            for(int j=0;j<matrix[0].length;j++){
//                if(matrix[i][j]==target){
//                    return true;
//                }
//            }
//        }
//        return false;
//    }
//
//    private boolean fun(int[][] matrix, int target, int x, int y) {
//        if(matrix[x][y]>target){
//            return false;
//        } else if (matrix[x][y]==target) {
//            return true;
//        }
//        boolean flag1 = false,flag2 = false;
//        if(x+1<matrix.length&&matrix[x+1][y]<=target){
//            flag1=fun(matrix,target,x+1,y);
//        }
//        if(y+1<matrix[0].length&&matrix[x][y+1]<=target){
//            flag2=fun(matrix,target,x,y+1);
//        }
//        return flag1||flag2;
//    }
//    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
//        if(headA==null||headB==null){
//            return null;
//        }
//        ListNode pA = headA;
//        ListNode pB = headB;
//        while(pA!=null){
//            while(pB!=null){
//                pB=pB.next;
//                if(pA==pB){
//                    return pA;
//                }
//            }
//            pB=headB;
//            pA=pA.next;
//        }
//        return null;
//    }
//
//    public ListNode reverseList(ListNode head) {
//        if(head==null||head.next==null){
//            return head;
//        }
//        List<ListNode> list = new LinkedList<>();
//        while(head!=null){
//            list.addFirst(head);
//            head=head.next;
//        }
//
//        ListNode pre = list.getFirst();
//        ListNode cur = pre;
//        list.removeFirst();
//        while(!list.isEmpty()){
//            cur.next=list.getFirst();
//            list.removeFirst();
//            if(!list.isEmpty())
//                cur=cur.next;
//        }
//        cur.next=null;
//        return pre;
//    }
//
//    public ListNode removeNthFromEnd(ListNode head, int n) {
//        ListNode dummy = new ListNode(0, head);
//        int length = getLength(head);
//        ListNode cur = dummy;
//        for (int i = 1; i < length - n + 1; ++i) {
//            cur = cur.next;
//        }
//        cur.next = cur.next.next;
//        ListNode ans = dummy.next;
//        return ans;
//    }
//
//    public int getLength(ListNode head) {
//        int length = 0;
//        while (head != null) {
//            ++length;
//            head = head.next;
//        }
//        return length;
//    }
//
//    public ListNode swapPairs(ListNode head) {
//        if (head == null || head.next == null) {
//            return head;
//        }
//        ListNode dummy = new ListNode(0, head);
//        ListNode prev = dummy;
//        ListNode cur = head;
//        while (cur != null && cur.next != null) {
//            ListNode next = cur.next.next;
//            prev.next = cur.next;
//            cur.next.next = cur;
//            cur.next = next;
//            prev = cur;
//            cur = next;
//        }
//        return dummy.next;
//    }
//
//
//    public static void main(String[] args) {
//        int[][] matrix = {{1,2,3,4},{1,2,3,4},{1,2,3,4},{1,2,3,4}};
//        code0827 solution = new code0827();
//        solution.rotate(matrix);
//        for(int i=0;i<matrix.length;i++){
//            for(int j=0;j<matrix[0].length;j++){
//                System.out.print(matrix[i][j]+" ");
//            }
//            System.out.println();
//        }
//    }
//}
